GATE CSE 2016 SET-2
Q41.
Suppose the functions F and G can be computed in 5 and 3 nano seconds by functional units U_{F} and U_{G}, respectively. Given two instances of U_{F} and two instances of U_{G}, it is required to implement the computation F(G(X_{i})) for 1\leq i\leq 10. Ignoring all other delays, the minimum time required to complete this computation is ________ nanoseconds.Q42.
Consider a 3GHz (gigahertz) processor with a three-stage pipeline and stage latencies \tau _{1}, \tau _{2}, and \tau _{3} such that \tau _{1}=3\tau _{2}/4=2\tau _{3}. If the longest pipeline stage is split into two pipeline stages of equal latency, the new frequency is _____GHz, ignoring delays in the pipeline registers.Q43.
Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more than 100 hours given that it is of Type 1 is 0.7, and given that it is of Type 2 is 0.4. The probability that an LED bulb chosen uniformly at random lasts more than 100 hours is _________.Q44.
Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ________.Q45.
Consider the following two-process synchronization solution. The shared variable turn is initialized to zero.Which one of the following is TRUE?Q46.
Consider the following expressions: (i) false (ii) Q (iii) true (iv) P\vee Q (v) \neg Q \vee P The number of expressions given above that are logically implied by P \wedge (P \Rightarrow Q) is ________.Q47.
Language L1 is defined by the grammar: S_{1}\rightarrow aS_{1}b|\varepsilon Language L2 is defined by the grammar: S_{2}\rightarrow abS_{2}|\varepsilon Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?Q48.
A binary relation R on \mathbb{N}\times \mathbb{N} is defined as follows: (a,b)R(c,d) if a \leq c or b \leq d. Consider the following propositions: P: R is reflexive Q: R is transitive Which one of the following statements is TRUE?Q49.
Consider a set U of 23 different compounds in a Chemistry lab. There is a subset S of U of 9 compounds, each of which reacts with exactly 3 compounds of U. Consider the following statements: I. Each compound in U \ S reacts with an odd number of compounds. II. At least one compound in U \ S reacts with an odd number of compounds. III. Each compound in U n S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE?Q50.
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Quicksort runs in \Theta (n^{2}) time II. Bubblesort runs in \Theta (n^{2}) time III. Merge sort runs in \Theta (n) time IV. Insertion sort runs in \Theta (n) time